1303D - Fill The Bag - CodeForces Solution

bitmasks greedy *1900

Please click on ads to support us..

Python Code: 

from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify
from math import inf, sqrt, ceil, log2
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
from typing import List
from bisect import bisect_left, bisect_right
import sys
import string
input=lambda:sys.stdin.readline().strip('\n')
mis=lambda:map(int,input().split())
ii=lambda:int(input())

T = ii()

for _ in range(T):
    N, M = mis()
    A = list(mis())

    C = [0] * 61
    sum = 0
    for a in A:
        C[int(log2(a))] += 1
        sum += a

    binn = format(N, 'b')[::-1]
    ans = 0
    if N > sum:
        print(-1)
        continue
    for i in range(len(binn)):
        if binn[i] == '0':
            pass
        elif C[i] > 0:
            C[i] -= 1
        else:
            j = i + 1
            while C[j] == 0:
                j += 1 
            C[j] -= 1
            C[j-1] += 1
            j -= 1
            ans += 1
            while j > i:
                ans += 1
                C[j-1] += 1
                j -= 1
        C[i+1] += C[i]//2
    print(ans)

C++ Code: 

#include <bits/stdc++.h>
#define int long long
using namespace std;

int cnt[65];

void solve(int tcId) {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < 64; i++)
        cnt[i] = 0;
    
    for (int i = 0; i < m; i++) {
        int v;
        cin >> v;
        int pow = 0;
        while (v > 1) {
            v /= 2;
            pow++;
        }

        cnt[pow]++;
    }

    int ans = 0;

    for (int bit = 0; bit < 64; bit++) {    
        if (n & ((int)1 << bit)) {
            if (cnt[bit] > 0) {
                cnt[bit]--;
            } else {
                // need to divide
                bool ok = false;
                int fst = bit + 1;
                for (; fst < 64; fst++) {
                    if (cnt[fst] > 0) {
                        ok = true;
                        break;
                    }
                }

                if (!ok) {
                    cout << "-1\n";
                    return;
                }

                cnt[fst]--;

                while (fst > bit) {
                    ans++;
                    fst--;
                    cnt[fst]++;
                }
            }
        }

        // merge
        int nxt = cnt[bit] / 2;
        cnt[bit + 1] += nxt;
        cnt[bit] %= 2;
    }

    cout << ans << '\n';
}

signed main() {
    bool multi = true;
    if (!multi) {
        solve(42);
    } else {
        int t;
        cin >> t;
        while (t--)
            solve(t);
    }
}


Comments

Submit
0 Comments
More Questions

1562B - Scenes From a Memory
1521A - Nastia and Nearly Good Numbers
208. Implement Trie
1605B - Reverse Sort
1607C - Minimum Extraction
1604B - XOR Specia-LIS-t
1606B - Update Files
1598B - Groups
1602B - Divine Array
1594B - Special Numbers
1614A - Divan and a Store
2085. Count Common Words With One Occurrence
2089. Find Target Indices After Sorting Array
2090. K Radius Subarray Averages
2091. Removing Minimum and Maximum From Array
6. Zigzag Conversion
1612B - Special Permutation
1481. Least Number of Unique Integers after K Removals
1035. Uncrossed Lines
328. Odd Even Linked List
1219. Path with Maximum Gold
1268. Search Suggestions System
841. Keys and Rooms
152. Maximum Product Subarray
337. House Robber III
869. Reordered Power of 2
1593C - Save More Mice
1217. Minimum Cost to Move Chips to The Same Position
347. Top K Frequent Elements
1503. Last Moment Before All Ants Fall Out of a Plank